Прізвище: Кордюк Ім'я: Роксолана Група: КН-116 Варіант: 7 Дата захисту:12.10.2014р. Кафедра: САПР Дисципліна: Теорія алгоритмів Перевірив: Андрущак Н.А. ЗВІТ до лабораторної роботи №1 на тему "МАШИНА ПОСТА" Мета роботи Вивчення формального визначення поняття алгоритму, пов’язаного із введеною Емілем Постом спеціальної математичної конструкції (машина Поста) і постулюванням тези про еквівалентність такого формалізму і поняття «алгоритм». Теоретичні відомості (Відповіді на контрольні запитання) 1. Що постулює так звана «теза Поста»? «Будь-який алгоритм можна представити у вигляді машини Поста». 2. Що таке алгоритм за Постом? Програма для машини Поста, що приводить до вирішення поставленої задачі. 3. Що таке машина Поста? Машина Поста — це абстрактна (тобто така, що не існує в арсеналі техніки), але дуже проста обчислювальна машина. 4. Які складові абстрактної машини Поста? неподільні носії інформації (комірки — біти), які можуть бути заповненими або незаповненими; обмежений набір елементарних дій — команд, кожна з яких виконується за один такт (крок). 5. Який набір команд виконує машина Поста? записати 1 (мітку), перейти до i-го рядка програми; записати 0 (стерти мітку), перейти до i-го рядка програми; переміститися вліво, перейти до i-го рядка програми; переміститися вправо, перейти до i-го рядка програми; зупинка; якщо 0, то перейти до i-го рядка програми, інакше перейти до j-го рядка програми. 6. Що таке початковий стан каретки? Під початковим станом каретки розумітимемо її положення навпроти порожньої комірки лівіше за найлівішу мітку на стрічці. 7. Що таке стан стрічки? Інформація про те, які комірки порожні, а які містять мітки, утворює стан стрічки. Іншими словами, стан стрічки — це розподіл міток по комірках. Стан стрічки змінюється у процесі роботи машини. 8. Що таке стан машини Поста? Стан машини Поста складається із стану стрічки і розташування каретки. 9. Навести перелік неприпустимих дій, які ведуть до аварійної зупинки машини. спроба записати 1 (мітку) в заповнену комірку; спроба стерти мітку в порожній комірці; нескінченне виконання (зациклення). 10.Що таке програма для машини Поста? Програмою для машини Поста називається непорожній список послідовно пронумерованих команд наступної структури: n K m, де n - порядковий номер команди, K − дія, яка виконується кареткою, m - номер наступної команди, яку необхідно виконати. 11. Коли програма застосовна до біжучого стану машини Поста? Ми можемо застосувати програму до біжучого стану машини Поста, якщо виконання програми не призведе до зациклювання, тобто рано чи пізно ми виконаємо команду «Зупинка». Індивідуальне завдання Число k представлено на стрічці машини Поста k+1 мітками, що йдуть підряд. Знайти залишок від ділення цілого додатнього числа k на 3, якщо відомо, що каретка знаходиться праворуч від заданого числа. Блок-схема алгоритму Текст (код) програми

Результати виконання програми
Аналіз результатів В результаті виконання програми ми отримуємо залишок від ділення цілого додатнього числа k на 3. Висновок У цій лабораторній роботі я ознайомилась з основними властивостями машини Поста, навчилась складати і використовувати програми для машини Поста. Перелік використаних посилань «МЕТОДИЧНІ ВКАЗІВКИ до лабораторної роботи No 1 з курсу «Алгоритми і структури даних» для студентiв базового напрямку 6.050101 «Комп’ютернi науки»